// 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
// 示例 1：
// `输入：nums = [1,1,2] 输出： [[1,1,2], [1,2,1], [2,1,1]] `
// 示例 2：
// `输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]`
// `used[i - 1] == true`，说明同一树枝`nums[i - 1]`使用过
// `used[i - 1] == false`，说明同一树层`nums[i - 1]`使用过
function permuteUnique(nums) {
    let result = []
    let path = []
    function backtracking(used = {}) {
        if (path.length === nums.length) {
            result.push([...path])
            return
        }
        for (let i = 0; i < nums.length; i++) {
            // 保证了在同一层中，相同数字只使用一次
            if (i > 0 && nums[i] === nums[i-1] && !used[i-1]) {
                continue
            }           
            if (!used[i]) {
                used[i] = true
                path.push(nums[i])
                backtracking(used)
                path.pop()
                used[i] = false
            } 
        }
    }
    nums.sort((x, y) => x - y)
    backtracking()
    return result
}

let nums = [1,1,2]
console.log(permuteUnique(nums))